R-Version: [Default] [32-bit] C:\Program Files\R\R-4.1.0

In folgendem Notebook werden anhand des MovieLense Datensatzes aus dem Paket RecommenderLab verschiedene Recommender erstellt. Es werden verschiedene Recommender und verschiedene Ähnlichkeiten verwendet, um diese zu vergleichen und auszuwerten. Ziel ist es, ein möglichst guter Recommender zu erstellen und zu verstehen wie dieser funktioniert. Zudem soll verstanden werden wie dieser bewertet wird und was in diesem Falle ein ‘guter’ Recommender bedeutet.

Dieses Notebook konzentriert sich auf Erkenntnisse von Auswertungen und Vergleichen. Um eine bessere Übersicht zu erhalten wurden grosse, sich widerholende Codes im Helperfile helper.R ausgelagert.

2.Binäre User-Liked-Items Matrix für alle Nutzer erzeugen.

movies_binary <- movies %>% mutate(rating = ifelse(rating > 3, 1, 0))
movies_wider <- pivot_wider(movies_binary, id_cols = user, names_from = item, values_from = rating)
rownames(movies_wider) <- movies_wider$user
Warning: Setting row names on a tibble is deprecated.
movies_wider['user'] <- NULL
user_movie_matrix <- as.matrix(movies_wider)
movies_wider

Für die Binäre User-Liked Matrix setzten wir die Grenze für ein gutes Rating bei >4. Also alle Filme, welche mit einem Rating von 3 oder weniger bewertet wurden, werden als schlecht bewertet definiert (also 0), wobei Filme mit Bewertungen von 4 oder 5 als gut bewertet definiert sind (1).

binary_non_na <- as(binarize(MovieLense, minRating = 4), 'matrix') * 1
binary_non_na[1:3, 1:3]
  Toy Story (1995) GoldenEye (1995) Four Rooms (1995)
1                1                0                 1
2                1                0                 0
3                0                0                 0

Um

3.Dimension der User-Liked-Items Matrix prüfen und ausgeben.

dim(user_movie_matrix)
[1]  943 1664

4.Movie-Genre Matrix für alle Filme erzeugen.

genres <- MovieLenseMeta
genres <- genres %>% select("title",'unknown':'Western')
rownames(genres) <- genres$title
genres['title'] <- NULL
movie_genre_matrix <- as.matrix(genres)
genres

5.Dimension der Movie-Genre Matrix prüfen und ausgeben.


A_test.data <- c(1,2,0,2,1,0,1,2,1)
A_test <- matrix(A_test.data, nrow=3)
A_test
     [,1] [,2] [,3]
[1,]    1    2    1
[2,]    2    1    2
[3,]    0    0    1
B_test.data <- c(1,2,0,2,1,0,1,2,1)
B_test <- matrix(B_test.data, nrow=3)
B_test
     [,1] [,2] [,3]
[1,]    1    2    1
[2,]    2    1    2
[3,]    0    0    1
result <- calc_cos_similarity_twomtrx(A_test, B_test)

if((dim(result) == dim(B_test)) && (dim(result) == dim(A_test))) {
  print("dimensions match")
} else {
  print("dimensions do not match")
}
[1] "dimensions match"
result
          [,1]      [,2]      [,3]
[1,] 1.0000000 0.8164966 0.4082483
[2,] 0.8164966 1.0000000 0.6666667
[3,] 0.4082483 0.6666667 1.0000000
class(movie_genre_matrix)
[1] "matrix" "array" 
user_movie_matrix[1:3, 1:3]
     Toy Story (1995) GoldenEye (1995) Four Rooms (1995)
[1,]                1                0                 1
[2,]                1               NA                NA
[3,]               NA               NA                NA
user_movie_matrix 

6.Anzahl unterschiedlicher Filmprofile bestimmen und visualisieren.

nr_diff_movies <- binary_non_na %*% movie_genre_matrix
nr_diff_movies <- as.data.frame(nr_diff_movies)

nr_diff_movies_mean <- rownames_to_column(nr_diff_movies)

nr_diff_movies_mean <- pivot_longer(nr_diff_movies_mean, cols = !rowname, names_to = 'genre', values_to = 'count')
nr_diff_movies_mean <- nr_diff_movies_mean %>% group_by(genre) %>% summarize(count = mean(count))

nr_diff_movies

TODO: Visualisierung der verschiedener Nutzerprofile ( siehe slide 13 Daniel) In dieser Matrix ist zu sehen wie viele Filme pro genre mit mehr als 3 bewertet wurden, jeweils pro User.

nr_diff_movies_mean
nr_diff_movies_mean %>% mutate(genre = fct_reorder(genre, count)) %>% 
  ggplot(aes(x = genre, y = count)) + 
  geom_col(fill = 'steelblue') +
  coord_flip() +
  scale_y_continuous(expand = c(0,0), limits = c(0, 30)) +
  geom_text(aes(label = round(count, 2)), hjust=-0.2, color = 'black') +
  labs(
    title = "Duchschnittliche Anzahl positiv bewerteter Filme pro Genre",
    x = element_blank(), 
    y = "Anzahl",
    fill = element_blank()
  ) +
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

7.User-Genre-Profil Matrix mit Nutzerprofilen im Genre-Vektorraum erzeugen.

##8.Dimension der User-Genre-Profil Matrix prüfen und ausgeben.

9.Anzahl unterschiedlicher Nutzerprofile bestimmen, wenn Stärke der GenreKombination (a) vollständig bzw. (b) nur binär berücksichtigt wird.

Ähnlichkeit von Nutzern und Filmen

1.Cosinus-Ähnlichkeit zwischen User-Genre- und Movie-Genre-Matrix berechnen.

Test


A_test.data <- c(1.5,2.5, 1.,0.5)
A_test <- matrix(A_test.data, nrow=2)
A_test
     [,1] [,2]
[1,]  1.5  1.0
[2,]  2.5  0.5
B_test.data <- c(0.5,1., 1.5,2.)
B_test <- matrix(B_test.data, nrow=2)
B_test
     [,1] [,2]
[1,]  0.5  1.5
[2,]  1.0  2.0
result <- calc_cos_similarity_twomtrx(A_test, B_test)

if((dim(result) == dim(B_test)) && (dim(result) == dim(A_test))) {
  print("dimensions match")
} else {
  print("dimensions do not match")
}
[1] "dimensions match"
check.data <- c(0.79, 0.5, 0.87, 0.61)
check <- matrix(check.data, nrow=2)

if(max(abs(check - result)) < 1e-2){
  print("check match")
} else{
  print("check differs from result")
}
[1] "check match"

In diesem Beispiel wurde für zwei 2x2 Matrizen mit zufällig gewählten Werten die cosine similarity berechnet. Diese Berechnung wurde ebenfalls von Hand gemacht und mit der Implementierung abgegelichen. Zusätzlich wurden die Dimensionen der Inputvariablen mit deren des Resultates abgeglichen. Die Berechnung der Cosine Similarity sollte so korrekt sein.

Anschliessend wird die Cosine Similarity der user-genre und movie-genre Matrixberechnet.

user_movie_non_na <- user_movie_matrix
user_movie_non_na[is.na(user_movie_non_na)] <- 0
user_movie_non_na[1:5, 1:5]
     Toy Story (1995) GoldenEye (1995) Four Rooms (1995) Get Shorty (1995) Copycat (1995)
[1,]                1                0                 1                 0              0
[2,]                1                0                 0                 0              0
[3,]                0                0                 0                 0              0
[4,]                0                0                 0                 0              0
[5,]                1                0                 0                 0              0

similarity <- calc_cos_similarity_twomtrx(user_movie_non_na, t(movie_genre_matrix))
summary(similarity)
    unknown              Action          Adventure         Animation         Children's          Comedy            Crime          Documentary           Drama        
 Min.   :0.0000000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.000000   Min.   :0.00000  
 1st Qu.:0.0000000   1st Qu.:0.05174   1st Qu.:0.02713   1st Qu.:0.00000   1st Qu.:0.00000   1st Qu.:0.03723   1st Qu.:0.02890   1st Qu.:0.000000   1st Qu.:0.07013  
 Median :0.0000000   Median :0.09530   Median :0.06691   Median :0.02291   Median :0.02440   Median :0.06872   Median :0.05600   Median :0.000000   Median :0.10636  
 Mean   :0.0005492   Mean   :0.11033   Mean   :0.07884   Mean   :0.03708   Mean   :0.03679   Mean   :0.08106   Mean   :0.06107   Mean   :0.008078   Mean   :0.11636  
 3rd Qu.:0.0000000   3rd Qu.:0.15322   3rd Qu.:0.11681   3rd Qu.:0.05657   3rd Qu.:0.05270   3rd Qu.:0.11617   3rd Qu.:0.08865   3rd Qu.:0.012612   3rd Qu.:0.15195  
 Max.   :0.2236068   Max.   :0.39834   Max.   :0.37064   Max.   :0.29513   Max.   :0.31642   Max.   :0.36430   Max.   :0.20658   Max.   :0.092582   Max.   :0.34499  
 NA's   :1           NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1          NA's   :1        
    Fantasy          Film-Noir           Horror           Musical           Mystery           Romance            Sci-Fi           Thriller            War         
 Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000  
 1st Qu.:0.00000   1st Qu.:0.00000   1st Qu.:0.00000   1st Qu.:0.00000   1st Qu.:0.02532   1st Qu.:0.05363   1st Qu.:0.04082   1st Qu.:0.05840   1st Qu.:0.05307  
 Median :0.00000   Median :0.02182   Median :0.02198   Median :0.02779   Median :0.05064   Median :0.08512   Median :0.07962   Median :0.09511   Median :0.09136  
 Mean   :0.01362   Mean   :0.03172   Mean   :0.03298   Mean   :0.04094   Mean   :0.05633   Mean   :0.09278   Mean   :0.09234   Mean   :0.10013   Mean   :0.09648  
 3rd Qu.:0.02581   3rd Qu.:0.04982   3rd Qu.:0.04961   3rd Qu.:0.06299   3rd Qu.:0.08280   3rd Qu.:0.12338   3rd Qu.:0.13499   3rd Qu.:0.13535   3rd Qu.:0.13476  
 Max.   :0.13319   Max.   :0.24225   Max.   :0.46658   Max.   :0.23905   Max.   :0.17252   Max.   :0.32757   Max.   :0.34179   Max.   :0.32695   Max.   :0.35029  
 NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1        
    Western       
 Min.   :0.00000  
 1st Qu.:0.00000  
 Median :0.00000  
 Mean   :0.02236  
 3rd Qu.:0.04029  
 Max.   :0.15157  
 NA's   :1        
plot_sim(similarity, "cosine similarity matrix between user-genre and movie-genre")

selection <- as.data.frame(similarity)[c(241, 414, 477, 526, 640, 710), ]
genres <- colnames(selection)
selection$users <- rownames(selection)
selection_long <- selection %>% pivot_longer(cols = genres)

ggplot(selection_long, aes(x=value, fill=users)) + geom_density(alpha=0.3) + 
    labs(title="Density plot Cosinus-Ähnlichkeiten ausgewählte users", subtitle="", x="similarity")

    
#plot_sim(selection, "cosine similarity user-genre and movie-genre selection")

Empfehlbare Filme

1. Bewertete Filme maskieren, d.h. “Negativabzug” der User-Items Matrix erzeugen, um anschliessend Empfehlungen herzuleiten.

2. Zeilensumme des “Negativabzuges” der User-Items Matrix für die User “5”, “25”, “50” und “150” ausgeben.

Hier zu sehen sind die anzahl nicht bewerteter filme pro user

3. 5-Zahlen Statistik der Zeilensumme des “Negativabzuges” der User-Items Matrix bestimmen.

Top-N Empfehlungen

1.Matrix für Bewertung aller Filme durch element-weise Multiplikation der Matrix der Cosinus-Ähnlichkeiten von Nutzern und Filmen und “Negativabzug” der User-Items Matrix erzeugen.

2.Dimension der Matrix für die Bewertung aller Filme prüfen.

3.Top-20 Listen pro Nutzer extrahieren.

4.Länge der Top-20 Listen pro Nutzer prüfen.

##5.Verteilung der minimalen Ähnlichkeit für Top-N Listen für N = 10, 20, 50 und 100 für alle Nutzer visuell vergleichen.

TODO: igewie visualisiere

##6.Top-20 Empfehlungen für Nutzer “5”, “25”, “50” und “150” visuell evaluieren.

TODO: clevelandplot

##7.Für Nutzer “133” und “555” Profil mit Top-N Empfehlungen für N = 20, 30, 40, 50 analysieren, visualisieren und diskutieren.

TODO: Clevelandplot + diskussion

LS0tDQp0aXRsZTogIkNvbnRlbnQtYmFzZWQgUmVjb21tZW5kZXIiDQphdXRob3I6ICJQYXNjYWwgQmVyZ2VyLCBMZWEgQsO8dGxlciAmIEpvw6tsIEdyb3NqZWFuIg0Kb3V0cHV0Og0KICBodG1sX25vdGVib29rOiBkZWZhdWx0DQogIHBkZl9kb2N1bWVudDogZGVmYXVsdA0KLS0tDQpSLVZlcnNpb246ICoqW0RlZmF1bHRdIFszMi1iaXRdIEM6XFxQcm9ncmFtIEZpbGVzXFxSXFxSLTQuMS4wKioNCg0KSW4gZm9sZ2VuZGVtIE5vdGVib29rIHdlcmRlbiBhbmhhbmQgZGVzIGBNb3ZpZUxlbnNlYCBEYXRlbnNhdHplcyBhdXMgZGVtIFBha2V0IFJlY29tbWVuZGVyTGFiIHZlcnNjaGllZGVuZSBSZWNvbW1lbmRlciBlcnN0ZWxsdC4gRXMgd2VyZGVuIHZlcnNjaGllZGVuZSBSZWNvbW1lbmRlciB1bmQgdmVyc2NoaWVkZW5lIMOEaG5saWNoa2VpdGVuIHZlcndlbmRldCwgdW0gZGllc2UgenUgdmVyZ2xlaWNoZW4gdW5kIGF1c3p1d2VydGVuLiBaaWVsIGlzdCBlcywgZWluIG3DtmdsaWNoc3QgZ3V0ZXIgUmVjb21tZW5kZXIgenUgZXJzdGVsbGVuIHVuZCB6dSB2ZXJzdGVoZW4gd2llIGRpZXNlciBmdW5rdGlvbmllcnQuIFp1ZGVtIHNvbGwgdmVyc3RhbmRlbiB3ZXJkZW4gd2llIGRpZXNlciBiZXdlcnRldCB3aXJkIHVuZCB3YXMgaW4gZGllc2VtIEZhbGxlIGVpbiAnZ3V0ZXInIFJlY29tbWVuZGVyIGJlZGV1dGV0Lg0KDQpEaWVzZXMgTm90ZWJvb2sga29uemVudHJpZXJ0IHNpY2ggYXVmIEVya2VubnRuaXNzZSB2b24gQXVzd2VydHVuZ2VuIHVuZCBWZXJnbGVpY2hlbi4gVW0gZWluZSBiZXNzZXJlIMOcYmVyc2ljaHQgenUgZXJoYWx0ZW4gd3VyZGVuIGdyb3NzZSwgc2ljaCB3aWRlcmhvbGVuZGUgQ29kZXMgaW0gSGVscGVyZmlsZSBgaGVscGVyLlJgIGF1c2dlbGFnZXJ0Lg0KDQpgYGB7ciBlY2hvPUZBTFNFLCBjYWNoZT1GQUxTRSwgcmVzdWx0cz1GQUxTRSwgY29tbWVudD1GQUxTRSwgd2FybmluZz1GQUxTRX0NCiMgbsO2dGlnZSBQYWNrZXRlDQpwYWNrYWdlcyA8LSBjKCJ0aWR5dmVyc2UiLCAiZGF0YS50YWJsZSIsICJsdWJyaWRhdGUiLCAiZ2dwbG90MiIsICJnZ3RoZW1lcyIsICJyZWNvbW1lbmRlcmxhYiIsICJrbml0ciIsICdwYWxzJywgJ1JDb2xvckJyZXdlcicsICdsYXR0aWNlJywgJ2dyaWQnLCAnZ3JpZEV4dHJhJykNCg0KIyBOb2NoIG5pY2h0IGluc3RhbGxpZXJ0ZSBQYWtldGUgaW5zdGFsbGllcmVuDQppbnN0YWxsZWRfcGFja2FnZXMgPC0gcGFja2FnZXMgJWluJSByb3duYW1lcyhpbnN0YWxsZWQucGFja2FnZXMoKSkNCg0KaWYgKGFueShpbnN0YWxsZWRfcGFja2FnZXMgPT0gRkFMU0UpKSB7DQogIGluc3RhbGwucGFja2FnZXMocGFja2FnZXNbIWluc3RhbGxlZF9wYWNrYWdlc10pDQp9DQoNCiMgTGFkZW4gZGVyIFBhY2tldGUNCmludmlzaWJsZShsYXBwbHkocGFja2FnZXMsIGxpYnJhcnksIGNoYXJhY3Rlci5vbmx5ID0gVFJVRSkpDQoNCiMgSW1wb3J0aWVyZW4gdm9uIEZ1bmt0aW9uZW5lIGF1cyBoZWxwZXIgZmlsZQ0Kc291cmNlKCJoZWxwZXIuUiIpDQoNCiMgY2hhbmdlIG9wdGlvbnMNCm9wdGlvbnMoZHBseXIuc3VtbWFyaXNlLmluZm9ybSA9IEZBTFNFKQ0KDQojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSBkYXRhIHdyYW5nbGluZyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tDQojIERhdGVuIGltcG9ydGllcmVuDQpkYXRhKE1vdmllTGVuc2UpDQoNCiMgZGF0YWZyYW1lIGVyc3RlbGxlbg0KbW92aWVzIDwtIGFzKE1vdmllTGVuc2UsICJkYXRhLmZyYW1lIikNCm1vdmllcyA8LSBtb3ZpZXMgJT4lIG11dGF0ZV9pZihpcy5jaGFyYWN0ZXIsIGFzLmZhY3RvcikNCg0KIyBicmVpdGUgdmVyc2lvbiBkZXMgZGF0YWZyYW1lIGVyc3RlbGxlbg0KIyBtb3ZpZXNfd2lkZXIgPC0gcGl2b3Rfd2lkZXIoDQojICAgbW92aWVzLA0KIyAgIGlkX2NvbHMgPSB1c2VyLA0KIyAgIG5hbWVzX2Zyb20gPSBpdGVtLA0KIyAgIHZhbHVlc19mcm9tID0gcmF0aW5nLA0KIyAgIHZhbHVlc19maWxsID0gTlVMTCwNCiMgKQ0KYGBgDQojIyAyLkJpbsOkcmUgVXNlci1MaWtlZC1JdGVtcyBNYXRyaXggZsO8ciBhbGxlIE51dHplciBlcnpldWdlbi4NCmBgYHtyfQ0KbW92aWVzX2JpbmFyeSA8LSBtb3ZpZXMgJT4lIG11dGF0ZShyYXRpbmcgPSBpZmVsc2UocmF0aW5nID4gMywgMSwgMCkpDQptb3ZpZXNfd2lkZXIgPC0gcGl2b3Rfd2lkZXIobW92aWVzX2JpbmFyeSwgaWRfY29scyA9IHVzZXIsIG5hbWVzX2Zyb20gPSBpdGVtLCB2YWx1ZXNfZnJvbSA9IHJhdGluZykNCnJvd25hbWVzKG1vdmllc193aWRlcikgPC0gbW92aWVzX3dpZGVyJHVzZXINCm1vdmllc193aWRlclsndXNlciddIDwtIE5VTEwNCnVzZXJfbW92aWVfbWF0cml4IDwtIGFzLm1hdHJpeChtb3ZpZXNfd2lkZXIpDQptb3ZpZXNfd2lkZXINCmBgYA0KRsO8ciBkaWUgQmluw6RyZSBVc2VyLUxpa2VkIE1hdHJpeCBzZXR6dGVuIHdpciBkaWUgR3JlbnplIGbDvHIgZWluIGd1dGVzIFJhdGluZyBiZWkgPjQuIEFsc28gYWxsZSBGaWxtZSwgd2VsY2hlIG1pdCBlaW5lbSBSYXRpbmcgdm9uIDMgb2RlciB3ZW5pZ2VyIGJld2VydGV0IHd1cmRlbiwgd2VyZGVuIGFscyBzY2hsZWNodCBiZXdlcnRldCBkZWZpbmllcnQgKGFsc28gMCksIHdvYmVpIEZpbG1lIG1pdCBCZXdlcnR1bmdlbiB2b24gNCBvZGVyIDUgYWxzIGd1dCBiZXdlcnRldCBkZWZpbmllcnQgc2luZCAoMSkuDQoNCmBgYHtyfQ0KYmluYXJ5X25vbl9uYSA8LSBhcyhiaW5hcml6ZShNb3ZpZUxlbnNlLCBtaW5SYXRpbmcgPSA0KSwgJ21hdHJpeCcpICogMQ0KYmluYXJ5X25vbl9uYVsxOjMsIDE6M10NCmBgYA0KVW0gDQoNCiMjIDMuRGltZW5zaW9uIGRlciBVc2VyLUxpa2VkLUl0ZW1zIE1hdHJpeCBwcsO8ZmVuIHVuZCBhdXNnZWJlbi4NCmBgYHtyfQ0KZGltKHVzZXJfbW92aWVfbWF0cml4KQ0KYGBgDQoNCiMjIDQuTW92aWUtR2VucmUgTWF0cml4IGbDvHIgYWxsZSBGaWxtZSBlcnpldWdlbi4NCmBgYHtyfQ0KZ2VucmVzIDwtIE1vdmllTGVuc2VNZXRhDQpnZW5yZXMgPC0gZ2VucmVzICU+JSBzZWxlY3QoInRpdGxlIiwndW5rbm93bic6J1dlc3Rlcm4nKQ0Kcm93bmFtZXMoZ2VucmVzKSA8LSBnZW5yZXMkdGl0bGUNCmdlbnJlc1sndGl0bGUnXSA8LSBOVUxMDQptb3ZpZV9nZW5yZV9tYXRyaXggPC0gYXMubWF0cml4KGdlbnJlcykNCmdlbnJlcw0KYGBgDQoNCiMjIDUuRGltZW5zaW9uIGRlciBNb3ZpZS1HZW5yZSBNYXRyaXggcHLDvGZlbiB1bmQgYXVzZ2ViZW4uDQpgYGB7cn0NCmRpbShtb3ZpZV9nZW5yZV9tYXRyaXgpDQpgYGANCmBgYHtyfQ0KY2xhc3MobW92aWVfZ2VucmVfbWF0cml4KQ0KYGBgDQpgYGB7cn0NCnVzZXJfbW92aWVfbWF0cml4WzE6MywgMTozXQ0KYGBgDQoNCmBgYHtyfQ0KdXNlcl9tb3ZpZV9tYXRyaXggDQpgYGANCg0KDQojIyA2LkFuemFobCB1bnRlcnNjaGllZGxpY2hlciBGaWxtcHJvZmlsZSBiZXN0aW1tZW4gdW5kIHZpc3VhbGlzaWVyZW4uDQpgYGB7cn0NCm5yX2RpZmZfbW92aWVzIDwtIGJpbmFyeV9ub25fbmEgJSolIG1vdmllX2dlbnJlX21hdHJpeA0KbnJfZGlmZl9tb3ZpZXMgPC0gYXMuZGF0YS5mcmFtZShucl9kaWZmX21vdmllcykNCg0KbnJfZGlmZl9tb3ZpZXNfbWVhbiA8LSByb3duYW1lc190b19jb2x1bW4obnJfZGlmZl9tb3ZpZXMpDQoNCm5yX2RpZmZfbW92aWVzX21lYW4gPC0gcGl2b3RfbG9uZ2VyKG5yX2RpZmZfbW92aWVzX21lYW4sIGNvbHMgPSAhcm93bmFtZSwgbmFtZXNfdG8gPSAnZ2VucmUnLCB2YWx1ZXNfdG8gPSAnY291bnQnKQ0KbnJfZGlmZl9tb3ZpZXNfbWVhbiA8LSBucl9kaWZmX21vdmllc19tZWFuICU+JSBncm91cF9ieShnZW5yZSkgJT4lIHN1bW1hcml6ZShjb3VudCA9IG1lYW4oY291bnQpKQ0KDQpucl9kaWZmX21vdmllcw0KYGBgDQpUT0RPOiBWaXN1YWxpc2llcnVuZyBkZXIgdmVyc2NoaWVkZW5lciBOdXR6ZXJwcm9maWxlICggc2llaGUgc2xpZGUgMTMgRGFuaWVsKQ0KSW4gZGllc2VyIE1hdHJpeCBpc3QgenUgc2VoZW4gd2llIHZpZWxlIEZpbG1lIHBybyBnZW5yZSBtaXQgbWVociBhbHMgMyBiZXdlcnRldCB3dXJkZW4sIGpld2VpbHMgcHJvIFVzZXIuDQpgYGB7cn0NCm5yX2RpZmZfbW92aWVzX21lYW4NCmBgYA0KDQpgYGB7cn0NCm5yX2RpZmZfbW92aWVzX21lYW4gJT4lIG11dGF0ZShnZW5yZSA9IGZjdF9yZW9yZGVyKGdlbnJlLCBjb3VudCkpICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gZ2VucmUsIHkgPSBjb3VudCkpICsgDQogIGdlb21fY29sKGZpbGwgPSAnc3RlZWxibHVlJykgKw0KICBjb29yZF9mbGlwKCkgKw0KICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApLCBsaW1pdHMgPSBjKDAsIDMwKSkgKw0KICBnZW9tX3RleHQoYWVzKGxhYmVsID0gcm91bmQoY291bnQsIDIpKSwgaGp1c3Q9LTAuMiwgY29sb3IgPSAnYmxhY2snKSArDQogIGxhYnMoDQogICAgdGl0bGUgPSAiRHVjaHNjaG5pdHRsaWNoZSBBbnphaGwgcG9zaXRpdiBiZXdlcnRldGVyIEZpbG1lIHBybyBHZW5yZSIsDQogICAgeCA9IGVsZW1lbnRfYmxhbmsoKSwgDQogICAgeSA9ICJBbnphaGwiLA0KICAgIGZpbGwgPSBlbGVtZW50X2JsYW5rKCkNCiAgKSArDQogIHRoZW1lX2NsYXNzaWMoKSArIA0KICB0aGVtZSgNCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksDQogICAgbGVnZW5kLnBvc2l0aW9uID0gJ2JvdHRvbScNCiAgKQ0KYGBgDQoNCiMjIDcuVXNlci1HZW5yZS1Qcm9maWwgTWF0cml4IG1pdCBOdXR6ZXJwcm9maWxlbiBpbSBHZW5yZS1WZWt0b3JyYXVtIGVyemV1Z2VuLg0KDQojIzguRGltZW5zaW9uIGRlciBVc2VyLUdlbnJlLVByb2ZpbCBNYXRyaXggcHLDvGZlbiB1bmQgYXVzZ2ViZW4uDQoNCiMjIDkuQW56YWhsIHVudGVyc2NoaWVkbGljaGVyIE51dHplcnByb2ZpbGUgYmVzdGltbWVuLCB3ZW5uIFN0w6Rya2UgZGVyIEdlbnJlS29tYmluYXRpb24gKGEpIHZvbGxzdMOkbmRpZyBiencuIChiKSBudXIgYmluw6RyIGJlcsO8Y2tzaWNodGlndCB3aXJkLg0KDQojIyDDhGhubGljaGtlaXQgdm9uIE51dHplcm4gdW5kIEZpbG1lbg0KDQojIyAxLkNvc2ludXMtw4RobmxpY2hrZWl0IHp3aXNjaGVuIFVzZXItR2VucmUtIHVuZCBNb3ZpZS1HZW5yZS1NYXRyaXggYmVyZWNobmVuLg0KDQojIyMgVGVzdA0KYGBge3J9DQoNCkFfdGVzdC5kYXRhIDwtIGMoMS41LDIuNSwgMS4sMC41KQ0KQV90ZXN0IDwtIG1hdHJpeChBX3Rlc3QuZGF0YSwgbnJvdz0yKQ0KQV90ZXN0DQoNCkJfdGVzdC5kYXRhIDwtIGMoMC41LDEuLCAxLjUsMi4pDQpCX3Rlc3QgPC0gbWF0cml4KEJfdGVzdC5kYXRhLCBucm93PTIpDQpCX3Rlc3QNCg0KcmVzdWx0IDwtIGNhbGNfY29zX3NpbWlsYXJpdHlfdHdvbXRyeChBX3Rlc3QsIEJfdGVzdCkNCg0KaWYoKGRpbShyZXN1bHQpID09IGRpbShCX3Rlc3QpKSAmJiAoZGltKHJlc3VsdCkgPT0gZGltKEFfdGVzdCkpKSB7DQogIHByaW50KCJkaW1lbnNpb25zIG1hdGNoIikNCn0gZWxzZSB7DQogIHByaW50KCJkaW1lbnNpb25zIGRvIG5vdCBtYXRjaCIpDQp9DQpjaGVjay5kYXRhIDwtIGMoMC43OSwgMC41MCwgMC44NywgMC42MSkNCmNoZWNrIDwtIG1hdHJpeChjaGVjay5kYXRhLCBucm93PTIpDQoNCmlmKG1heChhYnMoY2hlY2sgLSByZXN1bHQpKSA8IDFlLTIpew0KICBwcmludCgiY2hlY2sgbWF0Y2giKQ0KfSBlbHNlew0KICBwcmludCgiY2hlY2sgZGlmZmVycyBmcm9tIHJlc3VsdCIpDQp9DQoNCg0KYGBgDQoNCkluIGRpZXNlbSBCZWlzcGllbCB3dXJkZSBmw7xyIHp3ZWkgMngyIE1hdHJpemVuIG1pdCB6dWbDpGxsaWcgZ2V3w6RobHRlbiBXZXJ0ZW4gZGllIGNvc2luZSBzaW1pbGFyaXR5IGJlcmVjaG5ldC4gRGllc2UgQmVyZWNobnVuZyB3dXJkZSBlYmVuZmFsbHMgdm9uIEhhbmQgZ2VtYWNodCB1bmQgbWl0IGRlciBJbXBsZW1lbnRpZXJ1bmcgYWJnZWdlbGljaGVuLiBadXPDpHR6bGljaCB3dXJkZW4gZGllIERpbWVuc2lvbmVuIGRlciBJbnB1dHZhcmlhYmxlbiBtaXQgZGVyZW4gZGVzIFJlc3VsdGF0ZXMgYWJnZWdsaWNoZW4uIERpZSBCZXJlY2hudW5nIGRlciBDb3NpbmUgU2ltaWxhcml0eSBzb2xsdGUgc28ga29ycmVrdCBzZWluLg0KDQoNCkFuc2NobGllc3NlbmQgd2lyZCBkaWUgQ29zaW5lIFNpbWlsYXJpdHkgZGVyIHVzZXItZ2VucmUgdW5kIG1vdmllLWdlbnJlIE1hdHJpeGJlcmVjaG5ldC4NCg0KYGBge3J9DQp1c2VyX21vdmllX25vbl9uYSA8LSB1c2VyX21vdmllX21hdHJpeA0KdXNlcl9tb3ZpZV9ub25fbmFbaXMubmEodXNlcl9tb3ZpZV9ub25fbmEpXSA8LSAwDQp1c2VyX21vdmllX25vbl9uYVsxOjUsIDE6NV0NCmBgYA0KDQoNCmBgYHtyfQ0KDQpzaW1pbGFyaXR5IDwtIGNhbGNfY29zX3NpbWlsYXJpdHlfdHdvbXRyeCh1c2VyX21vdmllX25vbl9uYSwgdChtb3ZpZV9nZW5yZV9tYXRyaXgpKQ0KDQpgYGANCg0KYGBge3J9DQpzdW1tYXJ5KHNpbWlsYXJpdHkpDQpgYGANCg0KDQpgYGB7cn0NCnBsb3Rfc2ltKHNpbWlsYXJpdHksICJjb3NpbmUgc2ltaWxhcml0eSBtYXRyaXggYmV0d2VlbiB1c2VyLWdlbnJlIGFuZCBtb3ZpZS1nZW5yZSIpDQpgYGANCg0KDQpgYGB7cn0NCnNlbGVjdGlvbiA8LSBhcy5kYXRhLmZyYW1lKHNpbWlsYXJpdHkpW2MoMjQxLCA0MTQsIDQ3NywgNTI2LCA2NDAsIDcxMCksIF0NCmdlbnJlcyA8LSBjb2xuYW1lcyhzZWxlY3Rpb24pDQpzZWxlY3Rpb24kdXNlcnMgPC0gcm93bmFtZXMoc2VsZWN0aW9uKQ0Kc2VsZWN0aW9uX2xvbmcgPC0gc2VsZWN0aW9uICU+JSBwaXZvdF9sb25nZXIoY29scyA9IGdlbnJlcykNCg0KZ2dwbG90KHNlbGVjdGlvbl9sb25nLCBhZXMoeD12YWx1ZSwgZmlsbD11c2VycykpICsgZ2VvbV9kZW5zaXR5KGFscGhhPTAuMykgKyANCiAgICBsYWJzKHRpdGxlPSJEZW5zaXR5IHBsb3QgQ29zaW51cy3DhGhubGljaGtlaXRlbiBhdXNnZXfDpGhsdGUgdXNlcnMiLCBzdWJ0aXRsZT0iIiwgeD0ic2ltaWxhcml0eSIpDQogICAgDQojcGxvdF9zaW0oc2VsZWN0aW9uLCAiY29zaW5lIHNpbWlsYXJpdHkgdXNlci1nZW5yZSBhbmQgbW92aWUtZ2VucmUgc2VsZWN0aW9uIikNCg0KYGBgDQoNCiMjIyBFbXBmZWhsYmFyZSBGaWxtZQ0KIyMgMS4gQmV3ZXJ0ZXRlIEZpbG1lIG1hc2tpZXJlbiwgZC5oLiDigJxOZWdhdGl2YWJ6dWfigJ0gZGVyIFVzZXItSXRlbXMgTWF0cml4IGVyemV1Z2VuLCB1bSBhbnNjaGxpZXNzZW5kIEVtcGZlaGx1bmdlbiBoZXJ6dWxlaXRlbi4NCmBgYHtyfQ0KbW92aWVzX21hc2tlZCA8LSBtb3ZpZXNfd2lkZXINCm1vdmllc19tYXNrZWRbLTFdW21vdmllc19tYXNrZWRbLTFdID09IDFdIDwtIDANCm1vdmllc19tYXNrZWRbaXMubmEobW92aWVzX21hc2tlZCldIDwtIDENCm1vdmllc19tYXNrZWQNCmBgYA0KDQojIyAyLiBaZWlsZW5zdW1tZSBkZXMg4oCcTmVnYXRpdmFienVnZXPigJ0gZGVyIFVzZXItSXRlbXMgTWF0cml4IGbDvHIgZGllIFVzZXIg4oCcNeKAnSwg4oCcMjXigJ0sIOKAnDUw4oCdIHVuZCDigJwxNTDigJ0gYXVzZ2ViZW4uDQpgYGB7cn0NCmRlZmluZWRfdXNlciA8LSBjKDUsIDI1LCA1MCwgMTUwKQ0KZGVmaW5lZF91c2VyDQpyb3dTdW1zKG1vdmllc19tYXNrZWRbZGVmaW5lZF91c2VyLCAtMV0pDQpgYGANCkhpZXIgenUgc2VoZW4gc2luZCBkaWUgYW56YWhsIG5pY2h0IGJld2VydGV0ZXIgZmlsbWUgcHJvIHVzZXINCg0KIyMgMy4gNS1aYWhsZW4gU3RhdGlzdGlrIGRlciBaZWlsZW5zdW1tZSBkZXMg4oCcTmVnYXRpdmFienVnZXPigJ0gZGVyIFVzZXItSXRlbXMgTWF0cml4IGJlc3RpbW1lbi4NCmBgYHtyfQ0Kcm93c3Vtc19tYXNrZWQgPC0gcm93U3Vtcyhtb3ZpZXNfbWFza2VkWywgLTFdKQ0Kc3VtbWFyeShyb3dzdW1zX21hc2tlZCkNCmBgYA0KDQojIyBUb3AtTiBFbXBmZWhsdW5nZW4NCiMjIDEuTWF0cml4IGbDvHIgQmV3ZXJ0dW5nIGFsbGVyIEZpbG1lIGR1cmNoIGVsZW1lbnQtd2Vpc2UgTXVsdGlwbGlrYXRpb24gZGVyIE1hdHJpeCBkZXIgQ29zaW51cy3DhGhubGljaGtlaXRlbiB2b24gTnV0emVybiB1bmQgRmlsbWVuIHVuZCDigJxOZWdhdGl2YWJ6dWfigJ0gZGVyIFVzZXItSXRlbXMgTWF0cml4IGVyemV1Z2VuLg0KYGBge3J9DQpyYXRpbmdfbWF0cml4IDwtIHVzZXJfbW92aWVfbWF0cml4ICogbW92aWVzX21hc2tlZA0KYGBgDQoNCiMjIDIuRGltZW5zaW9uIGRlciBNYXRyaXggZsO8ciBkaWUgQmV3ZXJ0dW5nIGFsbGVyIEZpbG1lIHByw7xmZW4uDQpgYGB7cn0NCmRpbShyYXRpbmdfbWF0cml4KQ0KYGBgDQoNCiMjIDMuVG9wLTIwIExpc3RlbiBwcm8gTnV0emVyIGV4dHJhaGllcmVuLg0KYGBge3J9DQpnZXRfdG9wbl9yZWNvcyA8LSBmdW5jdGlvbihyYXRpbmdfbWF0cml4LCBuKXsNCiAgaGVyZMO2cGZlbCA8LSBhcyhyYXRpbmdfbWF0cml4LCAncmVhbG1hdHJpeG1hdHJpeCcpDQogIGhlcmTDtnBmZWwgPC0gYXMoaGVyZMO2cGZlbCwgJ2RhdGEuZnJhbWUnKQ0KICBoZXJkw7ZwZmVsIDwtIGFycmFuZ2UoZGVzYyhoZXJkw7ZwZmVsJHJhdGluZ3MpKSAlPiUNCiAgICBncm91cF9ieSh1c2VyKSAlPiUNCiAgICBzbGljZShoZWFkKG4pKSAlPiUNCiAgICB1bmdyb3VwKCkNCiAgcmV0dXJuKGhlcmTDtnBmZWwpDQp9DQoNCnJlY29tbWVuZGF0aW9uIDwtIGdldF90b3BuX3JlY29zKHJhdGluZ19tYXRyaXgsIDIwKQ0KcmVjb21tZW5kYXRpb24NCmBgYA0KDQojIyA0LkzDpG5nZSBkZXIgVG9wLTIwIExpc3RlbiBwcm8gTnV0emVyIHByw7xmZW4uDQpgYGB7cn0NCnN1bW1hcnkocmVjb21tZW5kYXRpb24pDQpgYGANCg0KIyM1LlZlcnRlaWx1bmcgZGVyIG1pbmltYWxlbiDDhGhubGljaGtlaXQgZsO8ciBUb3AtTiBMaXN0ZW4gZsO8ciBOID0gMTAsIDIwLCA1MCB1bmQgMTAwIGbDvHIgYWxsZSBOdXR6ZXIgdmlzdWVsbCB2ZXJnbGVpY2hlbi4NCmBgYHtyfQ0KYW5hbHl6ZV90b3BuX3JlY29zIDwtIGZ1bmN0aW9uKHJhdGluZ19tYXRyaXgsIGxpc3Qpew0KICByZWNvbXMgPC0gYygpDQogIGZvciAobiBpbiBsaXN0KSB7DQogICAgcmVjb21zIDwtIGFwcGVuZChyZWNvbXMsIGdldF90b3BuX3JlY29zKHJhdGluZ19tYXRyaXgsIG4pKQ0KICB9DQogIHJldHVybihyZWNvbXMpDQp9DQoNCmFuYWx5emVfdG9wbl9yZWNvcyhyYXRpbmdfbWF0cml4LCBjKDEwLCAyMCwgNTAsIDEwMCkpDQpgYGANClRPRE86IGlnZXdpZSB2aXN1YWxpc2llcmUNCg0KIyM2LlRvcC0yMCBFbXBmZWhsdW5nZW4gZsO8ciBOdXR6ZXIg4oCcNeKAnSwg4oCcMjXigJ0sIOKAnDUw4oCdIHVuZCDigJwxNTDigJ0gdmlzdWVsbCBldmFsdWllcmVuLg0KYGBge3J9DQpkZWZpbmVkX3VzZXJfbGlzdHMgPC0gZ2V0X3RvcG5fcmVjb3MocmF0aW5nbWF0cml4LCAyMCkgJT4lDQogIGZpbHRlcih1c2VyID09IGMoNSwgMjUsIDUwLCA1MCwgMTUwKSkgJT4lDQogIHVuZ3JvdXAoKQ0KDQpkZWZpbmVkX3VzZXJfbGlzdHMNCmBgYA0KVE9ETzogY2xldmVsYW5kcGxvdA0KDQojIzcuRsO8ciBOdXR6ZXIg4oCcMTMz4oCdIHVuZCDigJw1NTXigJ0gUHJvZmlsIG1pdCBUb3AtTiBFbXBmZWhsdW5nZW4gZsO8ciBOID0gMjAsIDMwLCA0MCwgNTAgYW5hbHlzaWVyZW4sIHZpc3VhbGlzaWVyZW4gdW5kIGRpc2t1dGllcmVuLg0KYGBge3J9DQphbmFseXplX3RvcG5fcmVjb3MocmF0aW5nX21hdHJpeFtjKDEzMywgNTU1KSxdLCBjKDIwLCAzMCwgNDAsIDUwKSkNCmBgYA0KVE9ETzogQ2xldmVsYW5kcGxvdCArIGRpc2t1c3Npb24NCg==